class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while(left < right)
        {
            while(left<right-1 && nums[left]==nums[left+1]) left++;
            while(left<right-1 && nums[right-1]==nums[right-2]) right--;

            int mid = (left+right) / 2;
            if(nums[mid] == target)
                return true;
            if(nums[mid] > nums[0])
            {
                if(target>=nums[left] && target<=nums[mid])
                    right = mid;
                else
                    left = mid+1;
            }
            else
            {
                if(target>=nums[mid] && target<=nums[right-1])
                    left = mid+1;
                else
                    right = mid;
            }
        }

        return false;
    }
};